package com.cctc.juc.source.Bitc.Faqs;

import sun.misc.Unsafe;

import java.util.concurrent.locks.LockSupport;

/**
 * [AQS（Abstract Queued Synchronizer）抽象队列同步器]
 * 要求：熟练、流畅的表述 CAS 全栈知识点，包括：
 * - 概述；
 * - 实现层面 [排队争抢线程]：线程同步原理；
 * - 使用层面：模板模式设计流程；
 * - 应用层面：典型应用场景；
 * - 总结。
 */
public abstract class AQS_AAAAA {
    /**
     * [Node 线程（等待）节点] 内部类。
     * AQS 是一个通过内置的 FIFO 双向队列来完成线程的排队工作的，内部通过节点 head 和 tail 记录队首和队尾节点，节点的类型通过内部类 Node 定义。
     * - 当线程抢锁失败后，AQS 会将该抢锁线程封装成一个 Node 节点，并通过 CAS 原子操作将其加入到同步队列的尾部；
     * - 当队首节点线程释放锁时，AQS 会尝试唤醒其后驱节点线程去占有锁，以达到线程同步的目的。
     * AQS 的队首节点和队尾节点都是懒加载的，即：
     * - 只有在线程竞争失败的情况下，AQS 才会创建一个 head 队首节点；
     * - 同样，只有在新线程也竞争失败，需要阻塞时，才会创建一个 tail 队尾节点。
     * 且都是通过 CAS 原子操作进行创建的。
     */
    static final class Node {
        // 抢锁线程
        volatile Thread thread;
        // 双向链表：前驱、后继节点
        volatile Node prev, next;
        /**
         * 后继节点：标识后继节点的抢占模式。
         * - 等于 SHARED，共享模式；
         * - 等于 EXCLUSIVE，独占模式。
         */
        Node nextWaiter;
        static final Node SHARED = new Node();
        static final Node EXCLUSIVE = null;
        /**
         * 当前节点的等待状态：
         * - 0：初始状态，表示当前节点正在初始化；此外，当 head 节点成功释放同步资源后，也会标记为 0，处于中间状态，等待被后继节点进行覆盖；
         * - 1：取消等待状态，表示当前节点因为中断或超时阻塞，需要从同步队列中移除；
         * - 2：信号（正常）等待状态，表示当前节点的后继节点处于正常阻塞状态，当该节点线程释放同步资源或被取消时，将会唤醒后继节点，获取同步资源；
         * - 3：条件等待状态，表示当前节点处于条件队列中，当其他节点线程调用 signal() 条件唤醒方法后，当前节点将会从条件队列中被唤醒，转移到同步队列，重新竞争同步资源；
         * - 4：传播等待状态，表示当前（head）节点处于（共享）传播等待状态，当线程获取到（共享）同步资源后，会将唤醒所有处于（共享）传播等待状态的后继节点，以获取（共享）同步资源。
         */
        volatile int waitStatus;
        static final int CANCELLED = 1, SIGNAL = -1, CONDITION = -2, PROPAGATE = -3;

        Node() {
        }

        Node(Thread thread, Node mode) {
            this.thread = thread;
            this.nextWaiter = mode;
        }

        Node(Thread thread, int waitStatus) {
            this.thread = thread;
            this.waitStatus = waitStatus;
        }

        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        final Node predecessor() throws NullPointerException {
            Node p;
            if ((p = prev) == null) throw new NullPointerException();
            return p;
        }
    }

    // --- [核心属性] --- //

    // 头、尾节点
    private transient volatile Node head, tail;
    // 锁的本质，使用一个状态值来表示锁，对锁的占用和释放通过此状态值来标识
    private volatile int state;

    protected AQS_AAAAA() {
    }

    // --- [模板流程] --- //

    /**
     * [模板流程] 以 {独占模式} 抢占同步资源，忽略中断，由子类提供具体的实现逻辑。
     * - 首先，调用一次 tryAcquire(arg) 钩子函数，尝试以独占模式抢占同步资源，成功则直接返回；
     * - 否则：
     * 1. addWaiter(mode)，使用独占模式将该抢锁线程封装成一个 Node 节点，将其加入到队列尾部；
     * 2. acquireQueued(Node)，（核心）启动 “自旋” 抢锁流程 -> 当前 Node 节点入队之后，一直在前驱节点上 “自旋”，当前驱节点是 head 队首节点时，再次触发 tryAcquire(arg) 钩子函数，尝试以独占模式抢占同步资源。为什么要这么做？？？
     * 1）维护同步队列的 FIFO 原则，Node 节点进入同步队列后，就进入了一个死循环的 “自旋” 过程，等待被前驱节点唤醒；
     * 2）只有 head 队首节点是成功获取同步资源的节点，等到队首节点线程释放同步资源后，将会唤醒后继节点，此时，后继节点需要检查自己的前驱节点是否为队首节点，如果是，则就可以再次调用 tryAcquire(arg) 钩子函数，占用同步资源。
     * 此外，为了不浪费 “空自旋” 造成的 CPU 资源浪费问题，Node 节点会在 “自旋” 过程中进行自我阻塞，等待被前驱节点唤醒后再重启循环，继续执行验证逻辑。
     * 3. selfInterrupt()，如果 2）成功，则进行自我中断，等待被前驱节点唤醒。
     *
     * @param arg 无特殊意义，可以表示任何你喜欢的东西，通常用于实现获取或释放同步资源的重入次数。
     */
    public final void acquire(int arg) {
        if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {
            selfInterrupt();
        }
    }

    /**
     * [模板流程] 以 {共享模式} 抢占同步资源，忽略中断，由子类提供具体的实现逻辑。
     * 说明：共享模式是一种传播模式，当 head 节点获取到共享同步资源后，会唤醒所有处于 PROPAGATE 状态下的后继节点，共享同步资源。
     * 除此之外，其他逻辑和独占模式的实现逻辑一致。
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

    /**
     * [模板流程] 释放（独占）同步资源，忽略中断，由子类提供具体的实现逻辑。
     * 调用 tryRelease(arg) 钩子函数，尝试释放同步资源，
     * - 如果成功，则唤醒后继节点，占有同步资源；
     * - 否则，返回 false。
     *
     * @param arg 无特殊意义，可以表示任何你喜欢的东西，通常用于实现获取或释放同步资源的重入次数。
     * @return true | false。
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0) unparkSuccessor(h);
            return true;
        }
        return false;
    }

    /**
     * [模板流程] 释放（共享）同步资源，忽略中断，由子类提供具体的实现逻辑。
     * 说明：共享模式是一种传播模式，当 head 节点获取到共享同步资源后，会唤醒所有处于 PROPAGATE 状态下的后继节点，共享同步资源。
     * 除此之外，其他逻辑和独占模式的实现逻辑一致。
     *
     * @param arg 无特殊意义，可以表示任何你喜欢的东西。
     * @return true | false。
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    // --- [钩子函数] --- //

    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    // --- [（获取同步资源）模板方法] --- //

    /**
     * 使用独占模式将该抢锁线程封装成一个 Node 节点，将其加入到队列尾部。
     * - 如果同步队列不为空，尝试通过 CAS 操作更新队尾节点（引用）为当前节点（引用），如果更新成功，则将当前 Node 节点加入到队列尾部；
     * - 否则，或者同步队列还未初始化，或者存在并发抢锁失败更新操作，进行 “自旋” 入队。
     */
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        Node prev = tail;
        if (prev != null) {
            node.prev = prev;
            if (casTail(prev, node)) {
                prev.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    /**
     * “自旋” 入队。
     * 通过 CAS “自旋” 将 Node 节点添加到队列尾部。
     * 1）如果同步队列为空，还未初始化，通过 CAS 操作创建一个新 Node 节点，初始化队尾节点和队首节点为新 Node 节点；
     * 2）“自旋”，同步队列不为空，尝试通过 CAS 操作更新队尾节点（引用）为当前节点（引用），如果更新成功，则将当前 Node 节点加入到队列尾部；
     * 3）否则，“自旋”，直到操作成功。
     */
    private Node enq(final Node node) {
        for (; ; ) {
            Node t = tail;
            if (t == null) {
                if (casHead(new Node())) tail = head;
            } else {
                node.prev = t;
                if (casTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

    /**
     * （核心）启动 “自旋” 抢锁流程。
     * 当前 Node 节点入队之后，一直在前驱节点上 “自旋”，当前驱节点是 head 队首节点时，再次触发 tryAcquire(arg) 钩子函数，尝试以独占模式抢占同步资源。
     * 为什么要这么做？？？
     * 1）维护同步队列的 FIFO 原则，Node 节点进入同步队列后，就进入了一个死循环的 “自旋” 过程，等待被前驱节点唤醒；
     * 2）只有 head 队首节点是成功获取同步资源的节点，等到队首节点线程释放同步资源后，将会唤醒后继节点，此时，后继节点需要检查自己的前驱节点是否为队首节点，如果是，则就可以再次调用 tryAcquire(arg) 钩子函数，占用同步资源。
     * 此外，为了不浪费 “空自旋” 造成的 CPU 资源浪费问题，Node 节点会在 “自旋” 过程中进行自我阻塞，等待被前驱节点唤醒后再重启循环，继续执行验证逻辑。
     */
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null;
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) {
                    interrupted = true;
                }
            }
        } finally {
            if (failed) {
                cancelAcquire(node);
            }
        }
    }

    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    private static boolean shouldParkAfterFailedAcquire(Node prev, Node node) {
        int waitStatus = prev.waitStatus;
        if (waitStatus == Node.SIGNAL) return true;
        if (waitStatus > 0) {
            do {
                node.prev = prev = prev.prev;
            } while (prev.waitStatus > 0);
            prev.next = node;
        } else {
            casWaitStatus(prev, waitStatus, Node.SIGNAL);
        }
        return false;
    }

    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    private void cancelAcquire(Node node) {
        if (node == null) return;
        node.thread = null;
        node.waitStatus = Node.CANCELLED;
        Node prev = node.prev;
        while (prev.waitStatus > 0) node.prev = prev = prev.prev;
        Node prevNext = prev.next;
        if (node == tail && casTail(node, prev)) casNext(prev, prevNext, null);
        else {
            int waitStatus;
            if (prev != head && ((waitStatus = prev.waitStatus) == Node.SIGNAL || (waitStatus <= 0 && casWaitStatus(prev, waitStatus, Node.SIGNAL))) && prev.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0) casNext(prev, prevNext, next);
            } else unparkSuccessor(node);
            node.next = node;
        }
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    // --- [（释放同步资源）模板方法] --- //

    private void unparkSuccessor(Node node) {
        int waitStatus = node.waitStatus;
        if (waitStatus < 0) casWaitStatus(node, waitStatus, 0);
        Node next = node.next;
        if (next == null || next.waitStatus > 0) {
            next = null;
            for (Node t = tail; t != null && t != node; t = t.prev) {
                if (t.waitStatus <= 0) next = t;
            }
        }
        if (next != null) LockSupport.unpark(next.thread);
    }

    // --- [CAS 操作] --- //

    private static final Unsafe UNSAFE = Unsafe.getUnsafe();
    private static final long headOffset, tailOffset;
    private static final long stateOffset;
    private static final long nextOffset;
    private static final long waitStatusOffset;

    static {
        try {
            Class<AQS_AAAAA> aqsClass = AQS_AAAAA.class;
            headOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("head"));
            tailOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("tail"));
            stateOffset = UNSAFE.objectFieldOffset(aqsClass.getDeclaredField("state"));
            Class<Node> nodeClass = Node.class;
            nextOffset = UNSAFE.objectFieldOffset(nodeClass.getDeclaredField("next"));
            waitStatusOffset = UNSAFE.objectFieldOffset(nodeClass.getDeclaredField("waitStatus"));
        } catch (NoSuchFieldException e) {
            throw new RuntimeException(e);
        }
    }

    private final boolean casHead(Node update) {
        return UNSAFE.compareAndSwapObject(this, headOffset, null, update);
    }

    private final boolean casTail(Node expect, Node update) {
        return UNSAFE.compareAndSwapObject(this, tailOffset, expect, update);
    }

    protected final boolean casState(int expect, int update) {
        return UNSAFE.compareAndSwapInt(this, stateOffset, expect, update);
    }

    protected final int getState() {
        return state;
    }

    private static final boolean casNext(Node node, Node expect, Node update) {
        return UNSAFE.compareAndSwapObject(node, nextOffset, expect, update);
    }

    private static final boolean casWaitStatus(Node node, int expect, int update) {
        return UNSAFE.compareAndSwapInt(node, waitStatusOffset, expect, update);
    }

}
